package LeetCode.LeetCodeHot;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 合并区间
 * @author lumin
 * @date 2022/04/17 00:00
 **/
public class Num56 {
//    public static int[][] merge(int[][] intervals) {
//        int i = 0;
//        int j = 1;
//        int Ai = 0;
//        int count = 0;
//        int[][] arr = new int[intervals.length][intervals[0].length];
//        while(j < intervals.length){
//            if(intervals[i][1] >= intervals[j][0]){
//                i++;
//                j++;
//                count++;
//            }else{
//                if(count == 0){
//                    arr[Ai][0] = intervals[j][0];
//                    arr[Ai][1] = intervals[j][1];
//                    Ai++;
//                    i++;
//                    j++;
//                }else{
//                    arr[Ai][0] = intervals[i - count][0];
//                    arr[Ai][1] = intervals[i][1];
//                    Ai++;
//                    count = 0;
//                }
//            }
//        }
//        return arr;
//    }
public int[][] merge(int[][] intervals) {
    if (intervals.length == 0) {
        return new int[0][2];
    }
    Arrays.sort(intervals, new Comparator<int[]>() {
        public int compare(int[] interval1, int[] interval2) {
            return interval1[0] - interval2[0];
        }
    });
    List<int[]> merged = new ArrayList<int[]>();
    for (int i = 0; i < intervals.length; ++i) {
        int L = intervals[i][0], R = intervals[i][1];
        if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
            merged.add(new int[]{L, R});
        } else {
            merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
        }
    }
    return merged.toArray(new int[merged.size()][]);
}

    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
    }
}